package own.stu.jobgib.playown.alg.unionFind;

public class UnionFind4 extends UnionFind_V2 {

    private int[] rank;   // rank[i]表示以i为根的集合所表示的树的层数

    public UnionFind4(int n) {
        super(n);

        rank = new int[n];

        for (int i = 0; i < n; i++) {
            rank[i] = 1;
        }
    }

    // 查找某一节点的根节点
    // O(h)复杂度, h为树的高度
    protected int find(int p) {

        //第二种路径压缩算法
//        if (p != ids[p])
//            ids[p] = find(ids[p]);
//        return ids[p];

        return ids[p] == p ? p : find(ids[p]);
    }

    // 合并元素p和元素q所属的集合
    // O(h)复杂度, h为树的高度
    public void union(int p, int q) {

        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot)
            return;

        if (rank[pRoot] < rank[qRoot]) {
            ids[pRoot] = qRoot;
        } else if (rank[qRoot] < rank[pRoot]) {
            ids[qRoot] = pRoot;
        } else {
            ids[pRoot] = qRoot;
            rank[qRoot] += 1;
        }

        this.count--;
    }
}
